import entity.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class InvertTree {
    /*
    * 226. 翻转二叉树
    * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    *
    * 树中节点数目范围在 [0, 100] 内
    * -100 <= Node.val <= 100
    * */
    public static void main(String[] args){

    }

    // 我的想法：深度优先递归啊当然是
    // 结果就是快的一批，但内存开销有点大
    public TreeNode mySolutionByRecursion(TreeNode root){
        invertTree(root);
        return root;
    }

    // 递归法书写步骤：
    // 1. 确定返回值和传入参数
    // 2. 确定递归结束条件
    // 3. 办正事
    private void invertTree(TreeNode root){
        if(root == null)
            return;
        else {
            TreeNode temp;
            temp = root.left;
            root.left = root.right;
            root.right = temp;
            invertTree(root.left);
            invertTree(root.right);
        }
    }

    // 广度优先
    public TreeNode mySolutionByIterate(TreeNode root){
        LinkedList<TreeNode> deque = new LinkedList<>();
        if(root != null) deque.add(root);
        TreeNode cur;
        while (!deque.isEmpty()){
            int len = deque.size();
            while (len > 0){
                cur = deque.pop();
                TreeNode temp;
                temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;
                if(cur.left != null) deque.add(cur.left);
                if(cur.right != null) deque.add(cur.right);
                len--;
            }
        }
        return root;
    }
}
